#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
    int ret = 0;
    void dfs(vector<int>& nums, int target, int pos, int sum)
    {
        if (pos == nums.size())
        {
            if (sum == target)
                ++ret;
            return;
        }

        dfs(nums, target, pos + 1, sum + nums[pos]);

        dfs(nums, target, pos + 1, sum - nums[pos]);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums, target, 0, 0);
        return ret;
    }

    vector<int> path;
    vector<vector<int>> res;
    void dfs(int n, int k, int pos)
    {
        if (k == path.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = pos; i <= n; ++i)
        {
            path.push_back(i);
            dfs(n, k, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
};